package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * FindSecondMinimumValue
 * <p>
 * 671. 二叉树中第二小的节点
 *
 * @author lupeng <lupeng@kuaishou.com>
 * Created on 2021-05-16
 */
public class FindSecondMinimumValue {

    public static void main(String[] args) {
        TreeNode root = TreeMain.array2tree(new Integer[]{2, 2, 5, null, null, 5, 7});
        System.out.println(new FindSecondMinimumValue().findSecondMinimumValue(root));
    }

    public int findSecondMinimumValue(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        inOrder(root, values);
        Collections.sort(values);
        for (int i = 1; i < values.size(); i++) {
            if (values.get(i) > values.get(i - 1)) {
                return values.get(i);
            }
        }
        return -1;
    }


    private void inOrder(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        inOrder(node.left, values);
        values.add(node.val);
        inOrder(node.right, values);
    }
}
